package com.example.arithmeticleetcode.learnArithmetic2.bloom;

/**
 * @program: arithmetic-leetcode
 * @description: 布隆过滤器 它是一个空间效率高的概率型数据结构，可以用来告诉你：一个元素一定不存在或者可能存在
 * @author: FangZhen
 * @create: 2020-12-30 11:36
 **/
public class BloomFilter<T> {

    /**
     * 二进制向量的长度（一共有多少个二进制位）
     */
    private int bitSize = 20;

    /**
     * 二进制向量
     */
    private long[] bits;

    /**
     * 哈希函数的个数
     */
    private int hashSize;

    /**
     * @param n 数据规模
     * @param p 误判率
     */
    public BloomFilter(int n, double p) {
        if (n <= 0 || p <= 0 || p >= 1) {
            throw new IllegalArgumentException("wrong n or p");
        }
        double ln2 = Math.log(2);
        //二进制向量的长度
        bitSize = (int) (-(n * Math.log(p)) / (ln2 * ln2));
        //哈希函数的个数
        hashSize = (int) (bitSize * ln2 / n);
        //二进制向量
        bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
    }

    /**
     * 添加元素
     *
     * @param value
     */
    public boolean put(T value) {
        nullCheck(value);

        //利用value生成两个参数
        int hash1 = value.hashCode();
        int hase2 = hash1 >>> 16;
        boolean result = false;
        for (int i = 1; i <= hashSize; i++) {
            int combineHash = hash1 + (hase2 * i);
            if (combineHash < 0) {
                combineHash = ~combineHash;
            }
            //生成一个二进制的索引
            int index = combineHash % bitSize;
            if (set(index)) result = true;
        }
        return result;
    }

    /**
     * 判断是否有元素
     *
     * @param value
     * @return
     */
    public boolean contains(T value) {
        nullCheck(value);
        //利用value生成两个参数
        int hash1 = value.hashCode();
        int hase2 = hash1 >>> 16;

        for (int i = 1; i <= hashSize; i++) {
            int combineHash = hash1 + (hase2 * i);
            if (combineHash < 0) {
                combineHash = ~combineHash;
            }
            //生成一个二进制的索引
            int index = combineHash % bitSize;
            //如果二进制为为0 返回false
            if (!get(index)) return false;
        }
        return true;
    }

    /**
     * 设置index位置二进制为1
     *
     * @param index
     */
    private boolean set(int index) {
        long value = bits[index / Long.SIZE];
        int bitValue = 1 << (index % Long.SIZE);
        bits[index / Long.SIZE] = value | bitValue;
        return (value & bitValue) == 0;
    }

    /**
     * 取出二进制的index位置的值
     *
     * @param index
     */
    private boolean get(int index) {
        long value = bits[index / Long.SIZE];
        return (value & (1 << (index % Long.SIZE))) != 0;
    }


    private void nullCheck(T value) {
        if (value == null) {
            throw new IllegalArgumentException("value must not be null");
        }
    }
}
